package pilhun.collections;

import java.util.Comparator;
import java.util.RandomAccess;

public class MyCollections {
	
	private static void quickSort(MyList list, int start, int end, Comparator comp){
		
	    if (start>=end) return;
	    Object pivot = list.get(start);
	    int i = start;
	    int j = end;
	 
	    while (i <= j){
	        while (comp.compare(pivot,list.get(i))>0){
	            i++;
	        }
	        while (comp.compare(pivot,list.get(j))<0){
	            j--;
	        }
	        if (i <= j){
	        	swap(list, i, j);
	            i++;
	            j--;
	        }
	    }
	    if (start < j) {
	        quickSort(list, start, j, comp);
	    }
	    if (i < end) {
	        quickSort(list, i, end, comp);
	    }
	}
	private static void bubbleSort(MyList list, Comparator comp){
		boolean swapped = true;
		while (swapped){
		   swapped = false;
		   for (int i = 0; i < list.size() - 1; i++) {
		      if (comp.compare(list.get(i), list.get(i + 1))>0) {
		         swap(list, i, i+1);
		         swapped = true;
		      }
		   }
		}
	}
	
	public static void sort(MyList list, Comparator comp){
		if(list instanceof RandomAccess){
			quickSort(list, 0, list.size()-1, comp);
		}else{
			bubbleSort(list, comp);
		}
	}
	
	public static void sort(MyList list){
		
		Comparator defaultComparator = new Comparator(){
			public int compare (Object o1, Object o2){
				return ((Comparable)o1).compareTo(o2);
			}
		};
		sort(list, defaultComparator);
	}
	
	
	public static void swap(MyList list, int i, int j){
		Object temp = list.get(i);
        list.set(i, list.get(j));
        list.set(j,temp);
	}
	
	public static void copy(MyList dest, MyList src){
		dest.clear();
		if(src instanceof RandomAccess){
			dest.addAll(src.toArray());
		}else{
			for(Object e:src){
				dest.add(e);
			}
		}
	}
	public static void reverse(MyList list){
		for (int i=0;i<list.size()/2;i++){
			swap(list, i, list.size()-i-1);
		}
	}
	
	
	private static int binarySearch(MyList list,Comparable key, int low, int high) {
	     if (high < low){
	         return -low-1;
	     }
	     int mid = (low + high) / 2;
	     if (key.compareTo(list.get(mid))<0){
	         return binarySearch(list, key, low, mid-1);
	     } else {
	    	 if (key.compareTo(list.get(mid))>0){
	    		 return binarySearch(list, key, mid+1, high);
	    	 } else{
	    		 return mid;
	    	 }
	    }
	}
	
	public static int binarySearch(RandomAccess list,Object key){
		return binarySearch((MyList)list,(Comparable) key, 0, ((MyList)list).size()-1);
	}
}
